/*
 * anima/pdb.cc - Physical/real pages database implementation.
 * Copyright (C) 2007  Mikhail Vorozhtsov
 * See the LICENSE section of the README file for details.
 */

/* $Id$ */

#include HEADER (anima,pdb.hh)
#include HEADER (anima,init.hh)
#include HEADER (anima,cpu.hh)
#include HEADER (anima,space.hh)
#include HEADER (anima,console.hh)
#include HEADER (utils,memory.hh)
#include HEADER (utils,minmax.hh)

START_NAMESPACE (anima)

typeof (pdb::regions) pdb::regions;

static pdb::entry_t lvl5[1 << (pdb::ADDR_BITS + 15 - 5 * mm::PAGE_BITS)]
  ALIGNED (1 << mm::PAGE_BITS);
static pdb::entry_t lvl4_0[1 << (mm::PAGE_BITS - 3)]
  ALIGNED (1 << mm::PAGE_BITS);
static pdb::entry_t lvl3_0[1 << (mm::PAGE_BITS - 3)]
  ALIGNED (1 << mm::PAGE_BITS);
static pdb::entry_t lvl2_0[1 << (mm::PAGE_BITS - 3)]
  ALIGNED (1 << mm::PAGE_BITS);
static pdb::lvl1e_t lvl1_0[1 << (mm::PAGE_BITS - 6)]
  ALIGNED (1 << mm::PAGE_BITS);

static pdb::lvl1e_t *free_lvl1e;

static const elbp::info_t *elbp_info;
static u64_t elbp_info_size;
static const elbp::mod_info_t *elbp_mod_info;

extern "C" void *kernel_start;
extern "C" void *kernel_end;

bool
pdb::add_region (u64_t addr, u64_t size, region_t::type_t type)
{
  static void *top = NULL;

  if (top == NULL
      || CUT ((u64_t) top, mm::PAGE_SIZE)
         != CUT ((u64_t) top + sizeof (region_t), mm::PAGE_SIZE))
    {
      top = mm::map ();

      if (!top)
        return false;
    }

  region_t *region = (region_t *) top;
  top += sizeof (region_t);

  region = new (region) region_t (
    ALIGN (addr, mm::PAGE_SIZE),
    CUT (addr + size, mm::PAGE_SIZE) - ALIGN (addr, mm::PAGE_SIZE), type);

  if (!regions.insert (region))
    return false;

  return true;
}

const pdb::region_t *
pdb::first_region ()
{
  return regions.get_min ();
}

const pdb::region_t *
pdb::find_region (u64_t addr)
{
  return regions.lookup_key (addr);
}

const pdb::region_t *
pdb::region_t::next () const
{
  return regions.get_next (this);
}

bool
pdb::init (const elbp::info_t *_elbp_info)
{
  static const u64_t LVL1_SIZE = SIZE (lvl1_0) * mm::PAGE_SIZE;

  elbp_info = _elbp_info;

  // Save these values to not map elbp_info later.
  elbp_info_size = elbp_info->size ();
  elbp_mod_info = elbp_info->mod_info;

  // Print memory map.
  {
    firmware::region_t region;
    const void *ptr = firmware::region_t::next (NULL, region);

    if (!ptr)
      {
        console::error ("Empty Memory Map.");
        return false;
      }

    console::print ("Memory Map:\n");

    for (; ptr; ptr = firmware::region_t::next (ptr, region))
      console::print (
        "  %p - %p, %s\n", region.addr, region.addr + region.size,
        firmware::region_t::type_string (region.type));
  }

  // Find best area for initial PDB entries and add it.
  {
    u64_t max_count = 0;
    u64_t max_addr = (u64_t) -1;

    firmware::region_t region;
    const void *ptr = firmware::region_t::next (NULL, region);

    for (; ptr; ptr = firmware::region_t::next (ptr, region))
      {
        if (!region.available_p ())
          continue;

        for (u64_t addr = CUT (region.addr, LVL1_SIZE);
             addr < ALIGN (region.addr + region.size, LVL1_SIZE);
             addr += LVL1_SIZE)
          {
            firmware::region_t region1;
            const void *ptr1 = firmware::region_t::next (NULL, region1);
            u64_t count = 0;

            for (; ptr1; ptr1 = firmware::region_t::next (ptr1, region1))
              {
                if (!region1.available_p ()
                    || region1.addr + region1.size <= addr
                    || addr + LVL1_SIZE <= region1.addr)
                  continue;

                for (u64_t p = utils::max (
                                 addr, ALIGN (region1.addr, mm::PAGE_SIZE));
                     p < utils::min (
                           addr + LVL1_SIZE,
                           CUT (region1.addr + region1.size, mm::PAGE_SIZE));
                     p += mm::PAGE_SIZE)
                  {
                    if (!page_used_p (p))
                      count += 1;
                  }
              }

            if (count > max_count)
              {
                max_count = count;
                max_addr = addr;

                if (max_count == SIZE (lvl1_0))
                  break;
              }
          }
      }

    lvl5[((paddr_t) max_addr).LVL5].set_ptr ((u64_t) lvl4_0).set_P ();
    lvl4_0[((paddr_t) max_addr).LVL4].set_ptr ((u64_t) lvl3_0).set_P ();
    lvl3_0[((paddr_t) max_addr).LVL3].set_ptr ((u64_t) lvl2_0).set_P ();
    lvl2_0[((paddr_t) max_addr).LVL2].set_ptr ((u64_t) lvl1_0).set_P ();

    ptr = firmware::region_t::next (NULL, region);

    for (; ptr; ptr = firmware::region_t::next (ptr, region))
      {
        if (!region.available_p ()
            || region.addr + region.size <= max_addr
            || max_addr + LVL1_SIZE <= region.addr)
          continue;

        for (u64_t p = utils::max (
                         max_addr, ALIGN (region.addr, mm::PAGE_SIZE));
             p < utils::min (
                   max_addr + LVL1_SIZE,
                   CUT (region.addr + region.size, mm::PAGE_SIZE));
             p += mm::PAGE_SIZE)
          {
            if (page_used_p (p))
              continue;

            lvl1e_t *lvl1e = &lvl1_0[(p - max_addr) / mm::PAGE_SIZE];

            lvl1e->entry.set_ptr (p)
              .set_usage (pdb::entry_t::USAGE_NONE).set_P ();

            if (!free_lvl1e)
              {
                lvl1e->next = lvl1e;
                lvl1e->prev = lvl1e;
                free_lvl1e = lvl1e;
              }
            else
              {
                lvl1e->prev = free_lvl1e->prev;
                lvl1e->next = free_lvl1e;
                lvl1e->prev->next = lvl1e;
                lvl1e->next->prev = lvl1e;
              }
          }
      }
  }

  return true;
}

pdb::lvl1e_t *
pdb::get (u64_t addr)
{
  paddr_t paddr = addr;
  entry_t *lvlXe = &lvl5[paddr.LVL5];

  if (!lvlXe->P)
    return NULL;

  lvlXe = &((entry_t *) lvlXe->get_ptr ())[paddr.LVL4];

  if (!lvlXe->P)
    return NULL;

  lvlXe = &((entry_t *) lvlXe->get_ptr ())[paddr.LVL3];

  if (!lvlXe->P)
    return NULL;

  lvlXe = &((entry_t *) lvlXe->get_ptr ())[paddr.LVL2];

  if (!lvlXe->P)
    return NULL;

  lvl1e_t *lvl1e = &((lvl1e_t *) lvlXe->get_ptr ())[paddr.LVL1];

  if (!lvl1e->entry.P)
    return NULL;

  return lvl1e;
}

pdb::lvl1e_t *
pdb::add (u64_t addr, bool used_p)
{
  paddr_t paddr = addr;
  entry_t *lvlX, *lvlXe = &lvl5[paddr.LVL5];

  if (!lvlXe->P)
    {
      lvlX = (entry_t *) mm::map ();

      if (!lvlX)
        return NULL;

      utils::zero (lvlX, mm::PAGE_SIZE);
      lvlXe->set_ptr ((u64_t) lvlX).set_P ();
    }
  else
    lvlX = (entry_t *) lvlXe->get_ptr ();

  lvlXe = &lvlX[paddr.LVL4];

  if (!lvlXe->P)
    {
      lvlX = (entry_t *) mm::map ();

      if (!lvlX)
        return NULL;

      utils::zero (lvlX, mm::PAGE_SIZE);
      lvlXe->set_ptr ((u64_t) lvlX).set_P ();
    }
  else
    lvlX = (entry_t *) lvlXe->get_ptr ();

  lvlXe = &lvlX[paddr.LVL3];

  if (!lvlXe->P)
    {
      lvlX = (entry_t *) mm::map ();

      if (!lvlX)
        return NULL;

      utils::zero (lvlX, mm::PAGE_SIZE);
      lvlXe->set_ptr ((u64_t) lvlX).set_P ();
    }
  else
    lvlX = (entry_t *) lvlXe->get_ptr ();

  lvlXe = &lvlX[paddr.LVL2];
  lvl1e_t *lvl1;

  if (!lvlXe->P)
    {
      lvl1 = (lvl1e_t *) mm::map ();

      if (!lvl1)
        return NULL;

      utils::zero (lvl1, mm::PAGE_SIZE);
      lvlXe->set_ptr ((u64_t) lvl1).set_P ();
    }
  else
    lvl1 = (lvl1e_t *) lvlXe->get_ptr ();

  lvl1e_t *lvl1e = &lvl1[paddr.LVL1];

  if (lvl1e->entry.P)
    return lvl1e;

  lvl1e->entry.set_ptr (addr);

  if (init::done_p ())
    {
    }
  else
    {
      space_t *main_space = init::get_main_space ().get ();

      if (main_space)
        {
          if (used_p)
            {
              if (lvl1e->entry.P)
                {
                  if (lvl1e->owner == init::get_main_space ()
                      && lvl1e->entry.usage == entry_t::USAGE_USER)
                    return lvl1e;
                  else
                    return NULL;
                }

              main_space->adopt (lvl1e);
            }
          else
            {
              if (lvl1e->entry.P)
                return lvl1e->owner == init::get_main_space () ? lvl1e : NULL;
              main_space->accept (lvl1e);
            }
        }
      else
        {
          if (used_p)
            {
              if (lvl1e->entry.P
                  && lvl1e->entry.usage != entry_t::USAGE_KERNEL)
                return NULL;

              lvl1e->entry.set_usage (entry_t::USAGE_KERNEL).set_P ();
              lvl1e->prev = NULL;
              lvl1e->next = NULL;
            }
          else
            {
              if (lvl1e->entry.P)
                return lvl1e;

              lvl1e->entry.set_usage (entry_t::USAGE_NONE).set_P ();

              if (!free_lvl1e)
                {
                  lvl1e->next = lvl1e;
                  lvl1e->prev = lvl1e;
                  free_lvl1e = lvl1e;
                }
              else
                {
                  lvl1e->prev = free_lvl1e->prev;
                  lvl1e->next = free_lvl1e;
                  lvl1e->prev->next = lvl1e;
                  lvl1e->next->prev = lvl1e;
                }
            }
        }
    }

  return lvl1e;
}

void
pdb::grant ()
{
  if (!free_lvl1e)
    return;

  space_t *main_space = init::get_main_space ().get ();
  lvl1e_t *lvl1e = free_lvl1e;

  do
    {
      lvl1e_t *next = lvl1e->next;
      main_space->accept (lvl1e);
      lvl1e = next;
    }
  while (lvl1e != free_lvl1e);

  free_lvl1e = NULL;
}

bool
pdb::reap ()
{
  for (const region_t *r = first_region (); r; r = r->next ())
    {
      if (!r->available_p ())
        continue;

      for (u64_t p = r->addr; p < r->addr + r->size; p += mm::PAGE_SIZE)
        {
          if (contains_p (p) || page_used_p (p))
            continue;
          if (!add (p))
            return false;
        }
    }

  return true;
}

bool
pdb::fill ()
{
  // Add all regions to the global list.
  {
    firmware::region_t region;

    for (const void *prev = firmware::region_t::next (NULL, region);
         prev; prev = firmware::region_t::next (prev, region))
      {
        if (!add_region (region.addr, region.size,
                         (region_t::type_t) region.type))
          return false;
      }
  }

  // Allocate LVL1 entries for all available pages.
  for (const region_t *r = first_region (); r; r = r->next ())
    {
      if (!r->available_p ())
        continue;

      for (u64_t p = r->addr; p < r->addr + r->size; p += mm::PAGE_SIZE)
        {
          if (page_used_p (p))
            continue;
          if (!add (p))
            return false;
        }
    }

  // Allocate LVL1 entries for kernel pages.
  for (u64_t p = CUT ((u64_t) &kernel_start, mm::PAGE_SIZE);
       p < ALIGN ((u64_t) &kernel_end, mm::PAGE_SIZE); p += mm::PAGE_SIZE)
    {
      if (!add (p, true))
        return false;
    }

  return true;
}

bool
pdb::page_used_p (u64_t addr)
{
  if (init::get_main_space ().null_p ())
    {
      if (utils::in_range_p (addr, (u64_t) &kernel_start, (u64_t) &kernel_end,
                             mm::PAGE_SIZE))
        return true;

      if (utils::in_range_p (
            addr, (u64_t) elbp_info, (u64_t) elbp_info + elbp_info_size,
            mm::PAGE_SIZE))
        return true;

      for (const elbp::mod_info_t *mod_info = elbp_mod_info; mod_info;
           mod_info = mod_info->next)
        {
          elbp::mod_info_t copy;
          u64_t mod_info_addr = (u64_t) mod_info;
          u64_t cmdline_len;

          if (mm::initialized_p ())
            {
              if (!mm::cp ((u64_t) mod_info, &copy, sizeof (copy)))
                return true;

              mod_info = &copy;
              cmdline_len = mm::length ((u64_t) mod_info->cmdline);
            }
          else
            cmdline_len = utils::length (mod_info->cmdline);

          if (utils::in_range_p (addr, mod_info_addr,
                                 mod_info_addr + sizeof (elbp::mod_info_t),
                                 mm::PAGE_SIZE)
              || utils::in_range_p (addr, mod_info->addr,
                                    mod_info->addr + mod_info->size,
                                    mm::PAGE_SIZE)
              || utils::in_range_p (
                   addr, (u64_t) mod_info->cmdline,
                   (u64_t) mod_info->cmdline + cmdline_len + 1, mm::PAGE_SIZE))
            return true;
        }
    }

  return firmware::page_used_p (addr) || cpu_t::page_used_p (addr);
}

pdb::lvl1e_t *
pdb::allocate ()
{
  lvl1e_t *lvl1e = NULL;

  if (!free_lvl1e)
    return NULL;

  lvl1e = free_lvl1e;

  free_lvl1e->prev->next = free_lvl1e->next;
  free_lvl1e->next->prev = free_lvl1e->prev;

  if (free_lvl1e == free_lvl1e->next)
    free_lvl1e = NULL;
  else
    free_lvl1e = free_lvl1e->next;

  lvl1e->entry.set_usage (pdb::entry_t::USAGE_KERNEL);
  lvl1e->prev = NULL;
  lvl1e->next = NULL;

  return lvl1e;
}

pdb::lvl1e_t *
pdb::allocate (u64_t addr)
{
  lvl1e_t *lvl1e = get (addr);

  if (!lvl1e || lvl1e->entry.usage != pdb::entry_t::USAGE_NONE)
    return NULL;

  lvl1e->prev->next = lvl1e->next;
  lvl1e->next->prev = lvl1e->prev;

  if (lvl1e == free_lvl1e)
    {
      if (free_lvl1e == free_lvl1e->next)
        free_lvl1e = NULL;
      else
        free_lvl1e = free_lvl1e->next;
    }

  lvl1e->entry.set_usage (pdb::entry_t::USAGE_KERNEL);
  lvl1e->prev = NULL;
  lvl1e->next = NULL;

  return lvl1e;
}

void
pdb::deallocate (pdb::lvl1e_t *lvl1e)
{
  if (!free_lvl1e)
    {
      lvl1e->next = lvl1e;
      lvl1e->prev = lvl1e;
      free_lvl1e = lvl1e;
    }
  else
    {
      lvl1e->prev = free_lvl1e->prev;
      lvl1e->next = free_lvl1e;
      lvl1e->prev->next = lvl1e;
      lvl1e->next->prev = lvl1e;
    }

  lvl1e->owner.null ();
  lvl1e->entry.set_usage (pdb::entry_t::USAGE_NONE);
}

END_NAMESPACE

